package com.ww.springboot.boot.util;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 描述：
 *
 * @author wanwei
 * @since 2021-07-26 09:38
 */
public class SudokuUtil {


    public static void solve(int[][] array) {
        int n = array.length;
        Stack<int[]> stack = new Stack<>();
        int x = 0;
        int y = 0;
        int[] ii = new int[2];
        ii[0] = x;
        ii[1] = y;
        stack.push(ii);
        //从左上角起
        while (x < n && y < n && !stack.empty()) {
            if (array[x][y] != 0) {
                if (x < n - 1) {
                    x++;
                } else {
                    y++;
                    x = 0;
                }
            } else {
                ii = new int[2];
                ii[0] = x;
                ii[1] = y;
                while (!stack.empty()) {
                    //入栈
                    //如果上一个值已经是9 则直接继续退
                    if (array[x][y] == 9) {
                        //还原值
                        array[x][y] = 0;
                        //回退 从栈中取出上一个坐标
                        ii = stack.pop();
                        x = ii[0];
                        y = ii[1];
                        continue;
                    }
                    array[x][y]++;
                    //判断是否合法
                    while (!judge(x, y, array) && !(array[x][y] >= n)) {
                        array[x][y]++;
                    }
                    if (!judge(x, y, array)) {
                        //还原值
                        array[x][y] = 0;
                        //回退 从栈中取出上一个坐标
                        ii = stack.pop();
                        x = ii[0];
                        y = ii[1];
                    } else {
                        stack.push(ii);
                        if (x == n - 1 && y == n - 1) {
                            break;
                        }
                        if (x < n - 1) {
                            x++;
                        } else {
                            y++;
                            x = 0;
                        }
                        break;
                    }
                }
            }
        }
        if (x == 0 && y == 0) {
            throw new RuntimeException("无解!");
        }
    }

    private static Boolean judge(int x, int y, int[][] arraysNew) {
        //横线不能重复
        Set<Integer> setX = new HashSet<>();
        Set<Integer> setY = new HashSet<>();
        for (int i = 0; i < arraysNew.length; i++) {
            if (arraysNew[x][i] == 0) {
                continue;
            }
            if (!setX.add(arraysNew[x][i])) {
                return false;
            }
        }
        //竖线不能重复
        for (int i = 0; i < arraysNew.length; i++) {
            if (arraysNew[i][y] == 0) {
                continue;
            }
            if (!setY.add(arraysNew[i][y])) {
                return false;
            }
        }

        Set<Integer> setNine = new HashSet<>();
        //9宫格不能重复
        int xx = x / 3;
        int yy = y / 3;

        for (int i = xx * 3; i < (xx + 1) * 3; i++) {
            for (int j = yy * 3; j < (yy + 1) * 3; j++) {
                if (arraysNew[i][j] == 0) {
                    continue;
                }
                if (!setNine.add(arraysNew[i][j])) {
                    return false;
                }
            }
        }
        return true;
    }

    public static String print(int[][] arrays) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arrays.length; i++) {
            for (int j = 0; j < arrays[i].length; j++) {
                sb.append(arrays[i][j]).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}
